/**
 * 哈希函数 -- 字符串转数字再压缩数字成数组下标 用于计算下标值
 * @param {*} str  字符串
 * @param {*} size
 * @returns
 * 1. 将字符串转成较大的数
 * 2. 将较大的数压缩到小范围
 */
function hasFun(str, size) {
	let hasCode = 0
	/// 霍纳算法
	for (let i = 0; i < str.length; i++) {
		hasCode = 37 * hasCode + str.charCodeAt(i)
	}
	return hasCode % size
}
/**
 *
 * @param {*} num 判断质数 用于数组扩容或者缩容
 * @returns
 */
function isPrime(num) {
	if (num == 1) return false
	let temp = parseInt(Math.sqrt(num))
	let i = 2
	while (i <= temp) {
		if (num % i === 0) {
			return false
		}
		i++
	}

	return true
}
function getPrim(num) {
	num++
	while (!isPrime(num)) {
		num++
	}
	return num
}

/**
 * 链地址放法
 */
class HasTable {
	constructor() {
		this.storage = []
		this.count = 0
		this.limit = 9
	}
	put(key, value) {
		const index = hasFun(key, this.limit)
		let bucket = this.storage[index] || []
		if (!this.storage[index]) {
			this.storage[index] = bucket
		}
		// 存在就修改
		for (let i = 0; i < bucket.length; i++) {
			const tuple = bucket[i]
			if (key === tuple[0]) {
				tuple[1] = value
				return
			}
		}
		// 不存在就添加
		bucket.push([key, value])
		this.count += 1
		// 判断是否要扩容
		if (this.count / this.limit >= 0.75) {
			let newLimit = this.limit * 2
			this.resize(getPrim(newLimit))
		}
	}
	get(key) {
		const bucket = this.storage[hasFun(key, this.limit)]
		if (!bucket) return null
		for (let i = 0; i < bucket.length; i++) {
			const tuple = bucket[i]
			if (key === tuple[0]) {
				return tuple
			}
		}
		return null
	}
	del(key) {
		let bucket = this.storage[hasFun(key, this.limit)]
		if (!bucket) return null
		for (let i = 0; i < bucket.length; i++) {
			const tuple = bucket[i]
			if (tuple[0] === key) {
				// delete this.storage[i][j] // delete 方式 原数组数组长度不变不太推荐
				bucket.splice(i, 1)
				this.count -= 1
				// 判断是否缩容
				console.log(this.count)
				console.log(this.limit)
				console.log(this.count / this.limit)
				if (this.limit > 7 && this.count / this.limit <= 0.25) {
					let newLimit = Math.floor(this.limit / 2)
					this.resize(getPrim(newLimit))
				}
				return tuple
			}
		}

		return null
	}
	resize(newLimit) {
		const olderStroe = this.storage
		this.storage = []
		this.count = 0
		this.limit = newLimit
		olderStroe.forEach((bucket) => {
			if (bucket) {
				bucket.forEach((tuple) => {
					if (tuple) {
						this.put(tuple[0], tuple[1])
					}
				})
			}
		})
	}
	isEmpty() {
		return this.count === 0
	}
	size() {
		return this.count
	}
	toString() {
		let str = []
		this.storage.forEach((item) => {
			item.forEach((it) => {
				str.push(it)
			})
		})
		return str
	}
}
